package algorithms.leaning.class25;

import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个二维数组matrix，其中的值不是0就是1，
 * 返回全部由1组成的最大子矩形，内部有多少个1
 *
 * @author guichang
 * @date 2021/6/27
 */

@SuppressWarnings("all")
public class Code4_单调栈_最大子矩形 {

    public static void main(String[] args) {
        int[][] nums = {
                {1, 1, 0, 1, 1},
                {1, 0, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1}
        };
        MyUtil.print(maxSubRectangle(nums));
    }

    /**
     * 必须以第i行做地基的最大矩形面积，第i行上有0则当前列归0其余上下相加
     * 每行都过一遍上提最大直方图面积
     */
    public static int maxSubRectangle(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int ans = 0;
        // 每次的地基
        int[] nums = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            // 地基累加
            for (int j = 0; j < matrix[0].length; j++) {
                nums[j] = matrix[i][j] == 0 ? 0 : nums[j] + matrix[i][j];
            }
            ans = Math.max(ans, maxArea(nums));
        }
        return ans;
    }

    private static int maxArea(int[] nums) {
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                Integer top = stack.pop(); // 当前计算的坐标
                int left = stack.isEmpty() ? 0 : stack.peek() + 1; // 最左边能到的位置
                int right = i - 1;// 最右能到的位置
                ans = Math.max(ans, nums[top] * (right - left + 1)); // 面积比较
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            Integer top = stack.pop();
            int left = stack.isEmpty() ? 0 : stack.peek() + 1; // 最左边能到的位置
            int right = nums.length - 1; // 最右能到的位置
            ans = Math.max(ans, nums[top] * (right - left + 1)); // 面积比较
        }
        return ans;
    }

}